/*
 * @lc app=leetcode.cn id=257 lang=cpp
 *
 * [257] 二叉树的所有路径
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right) {}
};

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string path = "";
    vector<string> paths;

    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root);
        return paths;
    }

    // 深度优先遍历
    void dfs(TreeNode* root) {
        // 递归终止条件：当前节点为空节点，直接返回
        if (root == nullptr) {
            return;
        }
        // 递归终止条件：当前节点为叶节点，保存结果
        if (root->left == nullptr && root->right == nullptr) {
            insertNode(root->val);
            paths.push_back(path);
            removeNode(root->val);
            return;
        }

        // 访问当前节点
        insertNode(root->val);

        // 访问左右子树
        if (root->left != nullptr) {
            dfs(root->left);
        }
        if (root->right != nullptr) {
            dfs(root->right);
        } 

        // 回溯当前节点
        removeNode(root->val);
    }

    // 保存当前节点的函数
    void insertNode(int value) {
        // 将当前节点保存到字符串中，如果不是首位需要添加箭头
        if (!path.empty()) {
            path.push_back('-');
            path.push_back('>');
        }
        string sValue = to_string(value);
        path = path + sValue;
        return;
    }

    // 删除当前节点的函数
    void removeNode(int value) {
        // 将当前节点移除字符串，如果不是首位需要删除箭头
        string sValue = to_string(value);
        for (int i = 0; i < sValue.size(); i++) {
            path.pop_back();
        }
        if (!path.empty()) {
            path.pop_back();
            path.pop_back();
        }
        return;
    }
};
// @lc code=end

